package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/flip-equivalent-binary-trees/description/
 *
 * 我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。
 *
 * 只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。
 *
 * 这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的树，则返回 true ，否则返回 false 。
 *
 *
 *
 * @author hanjuntao
 * @date 2025/10/1 0001
 */
public class L_951_翻转等价二叉树 {

    /**
     * 从题意可知，一个二叉树，可能通过有限的几步，选择几个节点进行翻转
     * 所以对于两个树，判断是否翻转等价。
     *
     * 判断两个树左右子树是否相等,由于存在翻转的可能性，所以需要判断是否互为镜像或者一致
     *
     * 即要么反转要么不反转，有一种情况满足就行
     * 不反转：左和左比，右和右比
     * 反转：左和右比，右和左比
     *
     * @param root1
     * @param root2
     * @return
     */
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }

        if (root1 == null || root2 == null) {
            return false;
        }

        if (root1.val != root2.val) {
            return false;
        }

        // 判断两个树左右子树是否相等,由于存在翻转的可能性，所以需要判断是否互为镜像或者一致

        // 1. root1的左子树和root2的左子树相等
        // 2. root1的右子树和root2的右子树相等

        // 或者
        // 1. root1的左子树和root2的右子树相等
        // 2. root1的右子树和root2的左子树相等

        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
                (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
    }
}
